% Copyright (C) 2017 Koz Ross <koz.ross@retro-freedom.nz>

% This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 
% International License. To view a copy of this license, visit 
% http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative 
% Commons, PO Box 1866, Mountain View, CA 94042, USA.

\documentclass{beamer}

\usepackage[utf8]{inputenc}
\usecolortheme{seahorse}
\usefonttheme{professionalfonts}
\usepackage{fontspec}
\setmainfont{DejaVu Sans}
\setbeamertemplate{navigation symbols}{}
\usepackage{caption}
\usepackage[font=itshape, begintext=``, endtext='']{quoting}
\usepackage{fancyvrb}
\usepackage{color}
\usepackage{booktabs}

\title{Memory management}
\subtitle{Or: why C++ is bad for your brain}
\titlegraphic{\includegraphics[scale=0.8]{img/logo.pdf}}
\author{Koz Ross}
\date{18th May, 2017}

\begin{document}

\begin{frame}[c]
  \titlepage{}
\end{frame}

\begin{frame}[c]
  \frametitle{Outline}
  \tableofcontents
\end{frame}

\section{Introduction}

\begin{frame}
  \frametitle{Why memory management?}
  \begin{itemize}
    \item All programming ultimately comes back to memory\pause{}
    \item Thanks to the memory wall getting ever higher, how we work with memory
      is more important than ever\pause{}
    \item New programming languages appear all the time --- knowing how memory
      is managed will give you an edge in deciding if it's any good\pause{}
    \item If you ever have to {\em implement\/} a language, this stuff is worth
      knowing!
  \end{itemize}
\end{frame}

\section{Preliminaries}

\begin{frame}
  \frametitle{Some terminology}
  \begin{itemize}
    \item When we talk about {\em memory\/} here, we refer to memory which
      is:\pause{}
      \begin{itemize}
        \item {\em Volatile\/} (i.e.\ lasts only as long as the program)\pause{}
        \item {\em Writeable\/} (i.e.\ we can change it, possibly several
          times)\pause{}
      \end{itemize}
    \item When we {\em allocate\/} memory, we reserve it for our use\pause{}
    \item When we don't need it anymore, we {\em deallocate\/} it, releasing it
      for someone else to play with (possibly even ourselves, for later)\pause{}
    \item A {\em reference\/} is a marker for a location in memory (basically, a
      C pointer)
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Two kinds of memory}
  \pause{}
  \begin{itemize}
    \item {\em Scoped:}\pause{}
      \begin{itemize}
        \item Tied to the scope in which it was allocated; once we leave that scope, 
          the memory gets deallocated immediately\pause{}
        \item Smaller (relatively); used for single variables or small data
          structures which aren't needed for long\pause{}
        \item Sometimes called `automatic', or `stack', memory (but we won't use
          those terms)\pause{}
      \end{itemize}
    \item {\em Non-scoped:}\pause{}
      \begin{itemize}
        \item Can persist past the scope in which it was allocated\pause{} 
        \item Larger (again, relatively); used for bigger structures that need
          to be around for a long time\pause{}
        \item Sometimes called `manual', or `heap', memory (but we won't use
          {\em those\/} terms either)\pause{}
      \end{itemize}
  \end{itemize}

  Out of the two, scoped memory is usually quite simple. For {\em non-scoped\/}
  memory, there are a few added challenges and trade-offs\ldots
\end{frame}

\begin{frame}
  \frametitle{Challenges with non-scoped memory}

  \begin{itemize}
    \item How much of the responsibility for deallocating the memory is on the
      programmer?\pause{}
    \item How predictable should it be?\pause{}
    \item What costs are we willing to pay for it?\pause{}
  \end{itemize}

  \bigskip

  Programming languages have converged on three different approaches to
  non-scoped memory management.
\end{frame}

\section{The three management approaches}

\begin{frame}
  \frametitle{Manual management}
  \pause{}
  \begin{itemize}
    \item The programmer must explicitly deallocate all non-scoped memory
      themselves (and deal with all the attendant issues)\pause{}
    \item Made famous by the C programming language, although C wasn't the first
      to use that method\pause{}
    \item Also a major reason why people hate writing C
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Reference counting}
  \pause{}
  \begin{itemize}
    \item When we allocate a block of non-scoped memory, we also make a counter
      for the number of references we have to that block (a {\em refcount\/})\pause{}
    \item Every time we take a new reference to a block of non-scoped memory, we
      increment that block's refcount; when that reference goes away, we
      decrement the correspoding refcount\pause{}
    \item When a block's refcount reaches $0$, we know that we can't reach it
      anymore, and the block gets deallocated
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Garbage collection}
  \pause{}
  \begin{itemize}
    \item Every reference, and all memory, is tracked by the programming
      language runtime automatically\pause{}
    \item When the runtime determines that a block of non-scoped memory has no
      references left to it, it will mark it as unused\pause{}
    \item At some later point, the runtime will deallocate all the unused blocks
      that exist at the time
  \end{itemize}
\end{frame}

\section{Advantages and disadvantages}

\begin{frame}[fragile]
  \frametitle{Answering the challenges}
  \begin{tabular}{cccc}
    \toprule
    & {\bf Responsibility} & {\bf Predictability} & {\bf Relative cost}\\
    \midrule
    Manual & All programmer & Total & Low\\
    Refcounting & Some programmer & Moderate & Moderate\\
    GC & All language & Low & High\\
    \bottomrule
  \end{tabular}\pause{}

  \bigskip

  This is a bit non-specific --- let's consider each one separately.
\end{frame}

\begin{frame}
  \frametitle{Manual management tradeoffs}
  \begin{itemize}
    \item Benefits:\pause{}
      \begin{itemize}
        \item Lowest resource cost (basically none)\pause{}
        \item Simplest for the language implementation and runtime\pause{}
        \item Completely predictable (thus, can be very heavily hand-optimized)\pause{}
      \end{itemize}
    \item Drawbacks:\pause{}
      \begin{itemize}
        \item {\em Painfully\/} tedious and error-prone (memory leaks, dangling
          pointers, wild pointers,\ldots)\pause{}
        \item Vulnerable to external memory fragmentation\pause{}
        \item {\em Requires\/} manual tuning to be effective (whether you know
          how or not)
      \end{itemize}
  \end{itemize}

  \bigskip

  Unsurprisingly, manual management is unpopular --- no programming language
  invented since the {\em eighties\/} uses it by default.\pause{} It was used
  more frequently before, as we had fewer alternatives and {\em much\/} more
  constrained computing resources (the computer C was designed on had 16{\em
  K\/} of RAM!).
\end{frame}

\begin{frame}
  \frametitle{Reference counting tradeoffs}
  \begin{itemize}
    \item Benefits:\pause{}
      \begin{itemize}
        \item Much less tedious\pause{}
        \item Deterministic and fairly predictable\pause{}
        \item Imposes very little overhead\pause{}
        \item Fairly simple for the language implementation and runtime\pause{}
      \end{itemize}
    \item Drawbacks:\pause{}
      \begin{itemize}
        \item Vulnerable to cyclic references\pause{}
        \item Vulnerable to external memory fragmentation\pause{}
        \item Very bad in heavily-concurrent environments\pause{}
      \end{itemize}
  \end{itemize}

  \bigskip

  Refcounting was first made famous by C++: initially, it had to be done by
  hand, but now has language-level support.\pause{} Surprisingly unpopular ---
  mostly used by pure functional languages like Haskell or C++ derivatives 
  like Swift and Rust.
\end{frame}

\begin{frame}
  \frametitle{Garbage collection tradeoffs}
  \begin{itemize}
    \item Benefits:\pause{}
      \begin{itemize}
        \item Very easy on the programmer (basically {\em never\/} have to think
          about memory management)\pause{}
        \item Can deal with external memory fragmentation and high contention
          without programmer intervention\pause{}
      \end{itemize}
    \item Drawbacks:\pause{}
      \begin{itemize}
        \item Trickiest for the runtime (especially for more modern garbage
          collectors)\pause{}
        \item Very unpredictable in general\pause{}
        \item (Relatively) resource-intensive\pause{}
      \end{itemize}
  \end{itemize}

  \medskip

  GC has maintained a rabid cult of detractors since it was invented in the
  1950s (most of whom write C++).\pause{} Many of their
  critiques are hilariously outdated or irrelevant today.\pause{} However, 
  there are still cases where the cost of GC is too high, or where its
  unpredictability is an issue.
\end{frame}

\begin{frame}
  \frametitle{So, which should we use?}
  \begin{itemize}
    \item Popularity-contest-wise, GC wins by a landslide:\pause{}
      \begin{itemize}
        \item Out of the TIOBE index's top $20$ languages, {\em twelve\/} use GC as
          their default method for managing non-scoped memory\pause{}
        \item Out of all the languages invented in the last $10$ years, all but
          two (Swift and Rust) use GC by default\pause{}
        \item Even Bjarne Stroustrup (inventor of C++) admitted C++ should have
          garbage collection (optionally)\ldots\pause{} nearly {\em twenty years
          ago\/} (take that, C++ cultists!)\pause{}
      \end{itemize}
    \item However, hype-following is {\em never\/} a good idea; a better plan is
      to consider your specific case and problem and go from there\pause{}
    \item The costs to GC are getting lower every day, partly because of better
      hardware, and partly because of better collectors\pause{}
    \item In short: {\em know your tradeoffs!}\pause{} (Well, I guess {\em don't
      be a cultist\/} also suits\ldots)
  \end{itemize}
\end{frame}

\section{Questions}

\begin{frame}[fragile, c]
  \frametitle{Questions?}
  \begin{center}
  \includegraphics[scale=0.27]{img/questions.pdf}
\end{center}
\end{frame}

\end{document}

